Kleene star 代數

Kleene algebra。Kleene star algebra

※de Morgan 代數でもある "Kleene algebra" は別物

$ Aを臺集合として、組$ (A,+_{:A\times A\to A},\cdot_{:A\times A\to A},^*_{:A\to A},0_{\in A},1_{\in A})は以下を滿たすならば Kleene star 代數と呼ぶ

組$ (A,+,\cdot,0,1)は冪等半環である

半順序 (poset)$ a\le bを$ \exist x_{\in A}(a+x=b)と定義する

Kleene star$ ^*は以下を滿たす

$ 1+a\cdot a^*\le a^*.

$ 1+a^*\cdot a\le a^*.

$ a\cdot x\le xならば$ a^*\cdot x\le x

$ x\cdot a\le xならば$ x\cdot a^*\le x

典型的には$ a^*:=1+a+a\cdot a+...と定義する

冪級數だ